In a digital video format, images are usually compressed for transmission and storage. Often sequential images in the video sequence differ only slightly. The difference from a previous, or following, image in the sequence can then be detected and encoded, rather than the entire picture. Such lossy compression techniques are widely used, such as in MPEG encoding.
During compression or encoding, each frame or image is divided into a grid of macroblocks, each containing 16×16 pixels. A macroblock from a current picture is compared to a range of macroblocks in a previous picture in the video sequence. Often a match or near-match is found at a different location. The difference in locations is known as a motion vector, since it indicates the movement of the macroblock between the two pictures. The motion vector rather than the entire macroblock can then be encoded for the new picture, saving storage space or transmission bandwidth.
Within the context of video encoding, it is often desirable, particularly within a motion estimator, to calculate a sum of absolute differences (SAD) between sets of pixels, one of which comprises a macroblock, or a partition thereof, the other set comprising reference data, when searching in a preceding frame for a matching macroblock.
For the purposes of illustration a 4×4 macroblock is considered herein in which the elements of a 4×4 macroblock are compared line by line with each overlapping 4×4 block of pixels in another frame. In general a 16×16 macroblock may be divided into 8×8 partitions which are subdivided into 4×4 sub-partitions.
In a known method, in order to locate a matching macroblock in another video frame, a sum of absolute differences is obtained between four fixed elements from one row of a 4×4 macroblock m3 m2 m1 m0, and a streaming row of reference data rx . . . r4 r3 r2 r1 r0 from the other frame. Typically r0, r1 etc. and m0, m1, etc. are unsigned 8-bit binary numbers.